package com.le.medium.class3;

import org.junit.Test;

/**
 * 有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打 包机上，
 * 放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人将每个机器上的物品进行移动从而到达物品数量相等才能打包。
 * 每个物品重量太大、 每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动。
 * 请计算在搬动最 小轮数的前提下，使每个机器上的物品数量相等。如果不能使每个机器上的物品相同， 返回-1。
 * 例如[1,0,5]表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后：
 * 第一轮：1  0 <- 5  =>   1  1  4
 * 第二轮：1 <-1<- 4  =>   2  1  3
 * 第三轮： 2  1 <- 3  =>  2  2  2 移动了3轮，每个机器上的物品相等，所以返回3
 */
public class Problem01_PackingMachine {

    public static int MinOps(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int size = arr.length;
        int sum = 0;
        for (int i = 0; i < size; i++) {
            sum += arr[i];
        }
        if (sum % size != 0) { // 物品累加和 % 机器个数
            return -1;
        }
        int avg = sum / size; // 每个机器上应该摆放的物品数量
        int res = 0; // 经过几轮
        int leftNum = 0;
        for (int i = 0; i < size; i++) {
            int L = leftNum - i * avg;
            int R = (sum - leftNum - arr[i]) - (size - i - 1) * avg;
            if (L < 0 && R < 0) {
                res = Math.max(res, Math.abs(L) + Math.abs(R));
            } else {
                res = Math.max(res, Math.max(Math.abs(L), Math.abs(R)));
            }
            leftNum += arr[i];
        }
        return res;
    }

    @Test
    public void test(){
        int[] arr = {1,0,5};
        System.out.println(MinOps(arr));
    }
}
